package com.hanxiaozhang.no10leetcode.dynamicprogramming;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈 最小路径和〉
 * <p>
 * 给定一个包含非负整数的n*m网格grid，请找出一条从左上角到右下角的路径，
 * 使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * <p>
 * 示例1:
 * 输入:
 * [
 * [1,3,1],
 * [1,5,1],
 * [4,2,1]
 * ]
 * 输出: 7
 * 解释: 因为路径 1→3→1→1→1 的总和最小。
 * <p>
 * 示例2:
 * 输入：
 * grid = [[1,2,3],[4,5,6]]
 * 输出：12
 * <p>
 * 思路：动态规划
 *  1.构建记忆表 int[n][m]
 *  2.初始化数据
 *  -- 初始化第一行数据 0
 *  -- 初始化第一列数据 0
 *  3. 构建状态转移方程
 *  -- 公式：当前项的最小路径和 = Math.min(左边，上边) + 原矩阵当前项
 *  4. 选择最优子结构（遍历记忆表，找出最优解）
 *   5. 回溯求解 -> int[n - 1][m - 1] 是最优解值
 *
 *
 * @author hanxinghua
 * @create 2023/12/4
 * @since 1.0.0
 */
public class No61MinPathSum {


    public static void main(String[] args) {

        int[][] grid1 = new int[][]{
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println("grid1 is " + minPathSum(grid1));

        int[][] grid2 = new int[][]{
                {1, 2, 3},
                {4, 5, 6}
        };
        System.out.println("grid2 is " + minPathSum(grid2));


    }

    /**
     * 最小路径和
     * <p>
     * 动态规划
     *
     * @param grid
     * @return
     */
    private static int minPathSum(int[][] grid) {

        //  n 行  m 列
        int temp = 0, n = grid.length, m = grid[0].length;

        // 1.构建记忆表
        int[][] result = new int[n][m];
        // 2.初始化数据
        // 初始化第一行数据
        for (int i = 0; i < m; i++) {
            temp += grid[0][i];
            result[0][i] = temp;
        }
        temp = 0;
        // 初始化第一列数据
        for (int i = 0; i < n; i++) {
            temp += grid[i][0];
            result[i][0] = temp;
        }
        // System.out.println(Arrays.deepToString(result));

        // 4. 选择最优子结构（遍历记忆表，找出最优解）
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 3. 构建状态转移方程
                // 公式：当前项的最小路径和 = Math.min(左边，上边) + 原矩阵当前项
                result[i][j] = Math.min(result[i][j - 1], result[i - 1][j]) + grid[i][j];
            }
        }
        // 5. 回溯求解
        return result[n - 1][m - 1];
    }

}
